Geometric spanner

A geometric spanner or a k-spanner graph or a k-spanner was initially introduced as a weighted graph over a set of points as its vertices which for every pair of vertices has a path between them of weight at most k times the spatial distance between these points for a fixed k. The parameter k is called the stretch factor or dilation factor of the spanner.[1]

In computational geometry, the concept was first discussed by L.P. Chew in 1986, [2] although the term "spanner" was not used in the original paper.

The notion of graph spanners has been known in graph theory: k-spanners are spanning subgraphs of graphs with similar dilation property, where distances between graph vertices are defined in graph-theoretical terms. Therefore geometric spanners are graph spanners of complete graphs embedded in the plane with edge weights equal to the distances between the embedded vertices in the corresponding metric.

Spanners may be used in computational geometry for solving some proximity problems. They have also found applications in other areas, such as in motion planning, in telecommunication networks: network reliability, optimization of roaming in mobile networks, etc.

Research

Chew's main result was that for a set of points in the plane there is a triangulation of this pointset such that for any two points there is a path along the edges of the triangulation with length at most \scriptstyle\sqrt 10 the Euclidean distance between the two points. The result was applied in motion planning for finding reasonable approximations of shortest paths among obstacles.

The best upper bound known for the Euclidean Delaunay triangulation is that it is a \scriptstyle{(4\sqrt{3}/9)\pi} \approx 2.418-spanner for its vertices.[3] The lower bound has been increased from \scriptstyle{{\pi}/2} to just over that, to 1.5846. [4]

Finding a spanner in the Euclidean plane with minimal dilation over n points with at most m edges is known to be NP-hard.[5]

Sparse spanners

Active research is ongoing concerning spanners with either small vertex degree or a small number of edges.

References

  1. ^ Narasimhan, Giri; Smid, Michiel (2007), Geometric Spanner Networks, Cambridge University Press, ISBN 0521815134 .
  2. ^ Chew, L. Paul (1986), "There is a planar graph almost as good as the complete graph", Proc. 2nd Annual Symposium on Computational Geometry, pp. 169–177, doi:10.1145/10515.10534 .
  3. ^ Keil, J. M.; Gutwin, C. A. (1992), "Classes of graphs which approximate the complete Euclidean graph", Discrete and Computational Geometry 7 (1): 13–28, doi:10.1007/BF02187821 .
  4. ^ Bose, P.; Devroye, L.; Loeffler, M.; Snoeyink, J.; Verma, V. (2009), "The spanning ratio of the Delaunay triangulation is greater than \scriptstyle{\pi/2}", Proc. 21st Canadian Conf. Computational Geometry, Vancouver, pp. 165–167 .
  5. ^ Klein, Rolf; Kutz, Martin (2007), "Computing Geometric Minimum-Dilation Graphs is NP-Hard", in Kaufmann, Michael; Wagner, Dorothea, Proc. 14th International Symposium in Graph Drawing, Karlsruhe, Germany, 2006, Lecture Notes in Computer Science, 4372, Springer Verlag, pp. 196–207, doi:10.1007/978-3-540-70904-6, ISBN 978-3-540-70903-9 .